package com.ctwom.algorithm.questions.Csort;

/**
 * 归并排序O(NlogN)
 * 思路：整体是递归，左边排好序，右边排好序，merge让整体有序
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {3,4,2,6,9,1,0,5};
        mergeSort(arr, 0, arr.length-1);
        for (int i: arr){
            System.out.println(i);
        }
    }
    public static void mergeSort(int[] arr, int L, int R){
        if(L == R){
            return;
        }
        int M = (L + R) / 2;
        mergeSort(arr, L, M);
        mergeSort(arr, M+1, R);
        merge(arr, L, M, R);
    }
    public static void merge(int[] arr, int L, int M, int R) {
        int[] help = new int[R-L+1];
        int i=0;
        int p1 = L;
        int p2 = M+1;
        while(p1 <= M && p2 <= R){
            help[i++] = arr[p1]<=arr[p2] ? arr[p1++] : arr[p2++];
        }
        while(p1 <= M){
            help[i++] = arr[p1++];
        }
        while(p2 <= R){
            help[i++] = arr[p2++];
        }
        for(int j=0;j<help.length;j++){
            arr[L+j] = help[j];
        }
    }
}
